#pragma once
#include <vector>
#include <iostream>
#include <utility>

template <class K, size_t M> //K是关键字类型，M是B树的阶数
struct BTreeNode{
    int _keys[M]; //M阶的B树节点中有M-1个关键字
    BTreeNode* _subs[M+1]; //M阶的B树节点中有M个孩子
    // 为了方便先插入后分裂，多开一个空间
    BTreeNode* _parent;
    int _n; //节点中存储key的个数
    
    BTreeNode()
    {
        for(int i = 0; i < M; ++i)
        {
            _keys[i] = K();
            _subs[i] = nullptr;
        }
        _subs[M] = nullptr;
        _n = 0;
        _parent = nullptr;
    }
};

template <class K, size_t M>
class BTree{
    typedef BTreeNode<K, M> Node;
    Node* _root;

public:
    BTree()
    :_root(nullptr)
    {}

    std::pair<Node*, int> find(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur)
        {
            //在一个节点中查找
            int i = 0;
            for(; i < cur->_n; ++i)
            {
                if(key < cur->_keys[i])
                {
                    break;
                }
                else if(key == cur->_keys[i])
                {
                    return std::make_pair(cur, i);
                }
            }
            parent = cur;
            cur = cur->_subs[i];
        }
        return std::make_pair(parent, -1); //找不到返回要插入的叶子节点和-1
    }

    bool insert(const K& key)
    {
        if(_root == nullptr)
        {
            _root = new Node;
            _root->_keys[0] = key;
            _root->_n++;
            return true;
        }

        std::pair<Node*, int> ret = find(key);
        if(ret.second != -1)
        return false; //key已经存在不允许插入
        Node* cur = ret.first;
        insert_node(cur, key, nullptr); //将关键字插入到叶子节点

        //检查是否需要进行分裂，cur==nullptr表示上一次是根节点分裂循环结束
        while(cur != nullptr && cur->_n == M) 
        {
            Node* parent = cur->_parent;
            Node* brother = new Node;
            int midi = cur->_n/2;
            int i = midi+1, j = 0;
            for(; i < cur->_n; ++i, ++j) //将中位数右侧的元素搬移到新建的兄弟节点
            {
                //拷贝key和他的孩子
                brother->_keys[j] = cur->_keys[i];
                brother->_subs[j] = cur->_subs[i];
                if(cur->_subs[i] != nullptr) //注意要修改孩子的父节点指针
                {
                    cur->_subs[i]->_parent = brother;
                }
                cur->_keys[i] = K(); //# 为方便调试将搬移后的数据清零
                cur->_subs[i] = nullptr; //# 实际可以不写
            }
            brother->_subs[j] = cur->_subs[i]; //最后一个右孩子也要拷走
            if(cur->_subs[i] != nullptr)
            {
                cur->_subs[i]->_parent = brother;
            }
            cur->_subs[i] = nullptr; //#
            brother->_n = j;

            if(parent == nullptr) //cur是根节点
            {
                _root = new Node;
                _root->_keys[0] = cur->_keys[midi];
                _root->_subs[0] = cur;
                _root->_subs[1] = brother;
                _root->_n = 1;
                cur->_parent = _root;
                brother->_parent = _root;
            }
            else 
            {
                insert_node(parent, cur->_keys[midi], brother); //将中位数和brother插入到父节点
                brother->_parent = parent; 
            }
            cur->_keys[midi] = K(); //#
            cur->_n -= (brother->_n+1); //记得修改cur节点的关键字个数
            
            cur = parent; //继续向上检查parent是否需要进行分裂
        }
        return true;
    }

    void inorder()
    {
        _inorder(_root);
        std::cout << std::endl;
    }

private:
    bool insert_node(Node* cur, const K& key, Node* child)
    {
        int end = cur->_n-1;
        while(end >= 0)
        {
            if(cur->_keys[end] > key)
            {
                //挪动key和他的右孩子
                cur->_keys[end+1] = cur->_keys[end];
                cur->_subs[end+2] = cur->_subs[end+1];
                --end;
            }
            else
            {
                break;
            }
        }
        cur->_keys[end+1] = key; //两种情况：1.end移动到-1位置 2.key>=[end]
        cur->_subs[end+2] = child;
        cur->_n++;
        return true;
    }
    
    void _inorder(const Node* cur)
    {
        int i = 0;
        for(; i < cur->_n; ++i)
        {
            if(cur->_subs[i] != nullptr)
            {
                _inorder(cur->_subs[i]);
            }
            std::cout << cur->_keys[i] << " ";
        }
        
        if(cur->_subs[i] != nullptr)
        {
            _inorder(cur->_subs[i]);
        }
    }
};